package BinaryTree;


import java.util.Stack;

public class LowestCommonAncestor {

    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode () {

        }
        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode LCA(TreeNode root,TreeNode p,TreeNode q) {
        if(root == null) {
            return null;
        }
        if(root == p||root ==q) {
            return root;
        }
        TreeNode leftTree = LCA(root.left,p,q);
        TreeNode rightTree = LCA(root.right,p,q);
        if(leftTree!=null&&rightTree!=null) {
            return root;
        }else if(leftTree!=null) {
            return leftTree;
        }else{
            return rightTree;
        }
    }

    public TreeNode LCA2(TreeNode root ,TreeNode p,TreeNode q) {
        if(root==null) {
            return null;
        }
        Stack<TreeNode> Pstack = new Stack<>();
        Stack<TreeNode> Qstack = new Stack<>();
        getPath(root,p,Pstack);
        getPath(root,q,Qstack);
        int sizeP = Pstack.size();
        int sizeQ = Qstack.size();
        if(sizeP > sizeQ) {
            int size = sizeP - sizeQ;
            for (int i = 0; i < size; i++) {
                Pstack.pop();
            }
        }else{
            int size = sizeQ - sizeP;
            for (int i = 0; i < size; i++) {
                Qstack.pop();
            }
        }
        while(!Pstack.isEmpty() && !Qstack.isEmpty()) {
            TreeNode node1 = Pstack.pop();
            TreeNode node2 = Qstack.pop();
            if(node1.equals(node2)) {
                return node1;
            }
        }
        return null;
    }

    private boolean getPath(TreeNode root , TreeNode node , Stack<TreeNode> stack) {
        //stack存放路径，先从左边开始找，一步一步递归寻找，如果找不到，
        if(root==null) {//归 的条件，遇到null视为没找到，返回false和上一个node的flg呼应
            return false;
        }
        stack.push(root);
        if(root==node) {
            return true;
        }
        boolean flg1 = getPath(root.left,node,stack);
        if(flg1) {
            return true;
        }
        boolean flg2 = getPath(root.right,node,stack);
        if(flg2) {
            return true;
        }
        stack.pop();
        return false;
    }
}
